package com.note.feng.dataStructureAlgorithm.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉搜索数BinarySearchTree
 *  二叉搜索树的概念：
 *      二叉搜索树也叫做二叉排序徐树，任何一个费叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大
 *      如果有相同的值，可以将该节点放在左子节点或右子节点
 *  二叉搜索树的深度优先遍历
 *      二叉树的深度遍历分为：前序遍历、中序遍历、后序遍历
 *      前序遍历：先输出父节点，再遍历左子树和右子树
 *      中序遍历：先遍历左子树，再输出父节点，再遍历右子树，中序遍历的结果是有序的
 *      后序遍历；先遍历左子树，再遍历右子树，最后输出父节点
 *  二叉搜索树非递归前序遍历：
 *      非递归前序遍历借助了栈
 *      根压栈->根出栈->压根的右孩子和左孩子->所有孩子已入栈则栈顶出栈->压入出栈节点的右孩子和左孩子->栈顶出栈......
 *  二叉搜索树的广度优先遍历：
 *      二叉树的广度优先遍历即层次遍历，使用层次遍历可以更快的找到问题的解
 *      常用与算法设计中，用作求最短路径
 *      层次遍历借助队列来实现
 *  二叉搜索树，具有天然递归性，可以使用递归的方式来删除节点
 *      删除叶子节点，则直接删除
 *      删除只有一颗树的节点，删除该节点，并将唯一的子树上移即可
 *      删除有两颗子树的节点，改节点的左子树中最大节点替换它或者该节点的右子树的最小节点替换它
 */
public class BST <E extends  Comparable<E>>{

    private Node root;
    private int size;

    public int getSize(){
        return size;
    }

    /**
     * BST添加新元素
     * @param e
     */
    public void add(E e){
        this.root = add(root, e);
    }

    /**
     * 给BST的某个节点添加新元素
     * @param node
     * @param e
     */
    private Node add(Node node, E e) {
        //如果node为空，将元素e添加到node节点
        if(node == null){
            size ++;
            return new Node(e);
        }
        //如果e小于node节点，添加到node的左子树上，否则添加到node的右子树上
        if(e.compareTo(node.e) < 0){
            node.left = add(node.left, e);
        }else{
            node.right = add(node.right, e);
        }
        return node;
    }

    public Node search(E e){
        return search(root, e);
    }

    private Node search(Node node, E e) {
        if(node == null){
            return null;
        }
        if(e.compareTo(node.e) == 0){
            return node;
        }else if(e.compareTo(node.e) < 0){
            return search(node.left, e);
        }else{
            return search(node.right, e);
        }
    }

    /**
     * 查找元素e的父节点
     * @param e
     * @return
     */
    public Node searchParent(E e){
        return searchParent(root, e);
    }

    /**
     * 查找元素e的父节点
     * @param node
     * @param e
     * @return
     */
    private Node searchParent(Node node, E e) {
        if(node == null){
            return null;
        }
        //如果node节点的左子树==e 或者右子树==e,则node节点就是元素e的父节点
        if((node.left != null && e.compareTo(node.left.e) == 0)
                || (node.right != null && e.compareTo(node.right.e) == 0)){
            return node;
        }else{
            //否则，需要去node节点的左子树或者右子树中去寻找
            if(e.compareTo(node.e) < 0){
                return searchParent(node.left, e);
            }else {
                return searchParent(node.right, e);
            }
        }
    }

    /**
     * BST前序遍历
     */
    public void prevOrder(){
        prevOrder(root);
    }

    private void prevOrder(Node node) {
        if(node == null){
            return;
        }
        System.out.println(node);
        prevOrder(node.left);
        prevOrder(node.right);
    }

    /**
     * BST中序遍历
     */
    public void middleOrder(){
        middleOrder(root);
    }

    private void middleOrder(Node node) {
        if(node == null){
            return ;
        }
        middleOrder(node.left);
        System.out.println(node);
        middleOrder(node.right);
    }

    /**
     * BST后序遍历
     */
    public void tailOrder(){
        tailOrder(root);
    }

    private void tailOrder(Node node) {
        if(node == null){
            return ;
        }
        tailOrder(node.left);
        tailOrder(node.right);
        System.out.println(node);
    }

    /**
     * 非递归前序遍历：
     * 非递归前序遍历借助了栈
     * 根压栈->根出栈->压根的右孩子和左孩子->所有孩子已入栈则栈顶出栈->压入出栈节点的右孩子和左孩子->栈顶出栈......
     */
    public void prevOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            Node node = stack.pop();
            System.out.println(node);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
    }

    /**
     * 非递归中序遍历
     */
    public void middleOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node node = root;
        while(node != null && !stack.empty()){
            while(node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            if(!stack.empty()){
                node = stack.pop();
                System.out.println(node);
                if(node.right != null){
                    stack.push(node.right);
                    node = node.right;
                }
            }
        }
    }

    /**
     * 非递归后序遍历
     */
    public void tailOrderNR(){
        Stack<Node> stack = new Stack<>();
        Node node = root;
        //刚出栈的节点
        Node prevNode = null;
        stack.push(root);
        while(node != null || !stack.empty()){
            while(node != null && node.left != null){
                stack.push(node.left);
                node = node.left;
            }
            if(!stack.empty()){
                //查看栈顶元素
                node = stack.peek();
                //如果栈顶元素的右节点为空或者已经出栈过了
                if(node.right == null || prevNode == node.right){
                    node = stack.pop();
                    System.out.println(node);
                    prevNode = node;
                    node = null;
                }else{
                    //遍历右节点
                    stack.push(node.right);
                    node = node.right;
                }
            }
        }
    }


    public static void main(String[] args) {
        BST<Integer> bst = new BST();
        bst.add(7);
        bst.add(3);
        bst.add(10);
        bst.add(5);
        bst.add(1);
        bst.add(9);
        bst.add(12);
//        System.out.println(bst.getSize());
//        System.out.println(bst.search(3));
//        System.out.println(bst.searchParent(12));
//        bst.prevOrder();
//        bst.middleOrder();
//        bst.tailOrder();
//        bst.prevOrderNR();
//        bst.middleOrderNR();
        bst.tailOrderNR();
    }


    private class Node {
        public E e;
        public Node left;
        public Node right;

        public Node(E e){
            this.e = e;
            this.left = null;
            this.right = null;
        }
        public Node(){

        }

        public String toString(){
            return e+"";
        }
    }
}
